#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
"""

from sys import maxsize as M


class FloydPath:
    def __init__(self, weight_matrix):
        self.n = len(weight_matrix)
        print(self.n)
        self.weight_matrix = weight_matrix
        self.path_matrix = self.mk_path_matrix()
        self.floyd()

    def floyd(self):
        for idx in range(self.n):
            self.refresh_by_node(idx)

    def refresh_by_node(self, idx):
        ''' 通过idx节点, 刷新矩阵最短路径 '''
        n = self.n
        weight_matrix = self.weight_matrix
        path_matrix = self.path_matrix

        for begin in range(n):
            for end in range(n):
                # print('loop %s, %s, %s' %(idx, begin, end))
                if begin == idx or end == idx or begin == idx:
                    continue
                weight = weight_matrix[begin][idx] + weight_matrix[idx][end]
                if weight < weight_matrix[begin][end]:
                    print('hit')
                    weight_matrix[begin][end] = weight
                    path_matrix[begin][end] = idx

    def mk_path_matrix(self):
        # l = []
        matrix = [ [begin] * self.n    for begin in range(self.n)]
        return matrix

    def __str__(self):
        return str(self.weight_matrix) + str(self.path_matrix)


def main():
    print("start main")
    weight_matrix = [
        [0, 3, M, 7],
        [8, 0, 2, M],
        [5, M, 0, 1],
        [2, M, M, 0],
    ]

    f = FloydPath(weight_matrix)
    print(f)


if __name__ == "__main__":
    main()
